#include<iostream>
#include<list>
using namespace std;

const int N = 1e5 + 10;
// 创建双向链表
int e[N], ne[N], pre[N], id, h;
int mp[N];
// 遍历链表
void print()
{
    for(int i = ne[h]; i; i = ne[i])
    {
        cout << e[i] << " ";
    }
    cout << endl;
}
// 头插
void push_back(int x)
{
    // 1.先存放x
    e[++ id] = x;
    mp[x] = id;
    // 2.先修改新结点的左右指针
    pre[id] = h;
    ne[id] = ne[h];
    // 3.修改哨兵位的右指针
    ne[h] = id;
    // 4.修改原先第一个结点的左指针
    pre[ne[h]] = id;
}
// 查找
int find(int x)
{
    return mp[x];
}
// 任意位置p后面插入x
void insert_back(int p, int x)
{
    e[++ id] = x;
    mp[x] = id;
    pre[id] = p;
    ne[id] = ne[p];
    ne[p] = id;
    pre[ne[p]] = id;
}
// 任意位置p前面插入x
void insert_front(int p, int x)
{
    e[++ id] = x;
    mp[x] = id;
    pre[id] = pre[p];
    ne[id] = p;
    ne[pre[p]] = id;
    pre[p] = id;
}
// 删除任意位置p的元素
void erase(int p)
{
    mp[e[p]] = 0;

    ne[pre[p]] = ne[p];
    pre[ne[p]] = pre[p];
}
// list 动态链表
void list_test()
{
    list<int> lt;
    for(int i = 1; i <= 5; i ++)
    {
        lt.push_back(i);
        print();
    }
    
    for(int i = 1; i <= 3; i ++) lt.pop_front(); 
}
int main()
{
    for(int i = 1; i <= 10; i ++)
        push_back(i);

    
    return 0;
}